package com.zhanghp.class035;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;

/**
 * 全O(1)的数据结构<br/>
 * 测试链接 : https://leetcode.cn/problems/all-oone-data-structure/
 *
 * @author zhanghp
 * @since 2024/4/17 13:53
 */
public class Code07_AllO1 {

    class AllOne {

        public Bucket head;

        public Bucket tail;

        /**
         * 用来inc，dec处理数据用
         */
        public Map<String, Bucket> map;

        public AllOne() {
            head = new Bucket("", 0);
            tail = new Bucket("", Integer.MAX_VALUE);
            map = new HashMap<>();
            head.next = tail;
            tail.last = head;
        }

        public void insert(Bucket cur, Bucket pos) {
            cur.next.last = pos;
            pos.next = cur.next;
            cur.next = pos;
            pos.last = cur;
        }

        public void remove(Bucket cur) {
            cur.last.next = cur.next;
            cur.next.last = cur.last;
        }

        public void inc(String key) {
            if (!map.containsKey(key)) {
                if (head.next.cnt != 1) {
                    Bucket newBucket = new Bucket(key, 1);
                    map.put(key, newBucket);
                    // 双向链表插入
                    insert(head, newBucket);
                } else {
                    map.put(key, head.next);
                    head.next.set.add(key);
                }
            } else {
                Bucket bucket = map.get(key);
                if (bucket.next.cnt != (bucket.cnt + 1)) {
                    Bucket newBucket = new Bucket(key, bucket.cnt + 1);
                    map.put(key, newBucket);
                    insert(bucket, newBucket);
                } else {
                    map.put(key, bucket.next);
                    bucket.next.set.add(key);
                }
                bucket.set.remove(key);
                // 移除set为空的情况，bucket移除双向链表
                if (bucket.set.isEmpty()) {
                    remove(bucket);
                }
            }

        }

        /**
         * 字符串 key 的计数减少 1 。如果 key 的计数在减少后为 0 ，那么需要将这个 key 从数据结构中删除。测试用例保证：在减少计数前，key 存在于数据结构中。
         *
         * @param key
         */
        public void dec(String key) {
            Bucket bucket = map.get(key);
            // 单独判断1的情况
            if (bucket.cnt == 1) {
                map.remove(key);
            } else {
                // 说明出现次数不为1次，要进行处理
                // 上一个桶是否和cnt-1相等
                if (bucket.last.cnt != (bucket.cnt - 1)) {
                    // 建立新桶
                    Bucket newBucket = new Bucket(key, bucket.cnt - 1);
                    // 存入map
                    map.put(key, newBucket);
                    // 插入新桶
                    insert(bucket.last, newBucket);

                } else {
                    // 存入map
                    map.put(key, bucket.last);
                    // 上一个桶的set进行存储
                    bucket.last.set.add(key);
                }
            }
            bucket.set.remove(key);
            if (bucket.set.isEmpty()) {
                remove(bucket);
            }
        }

        public String getMaxKey() {
            return tail.last.set.iterator().next();
        }

        public String getMinKey() {
            return head.next.set.iterator().next();
        }

        // 桶
         class Bucket {
            public HashSet<String> set;

            public int cnt;

            public Bucket last;

            public Bucket next;

            public Bucket(String s, int cnt) {
                this.cnt = cnt;
                this.set = new HashSet<>();
                set.add(s);
                last = next = null;
            }

        }
    }
}
